package io.zhengsh.vvip.leetcode.window;

import java.util.*;

/**
 * 30. 串联所有单词的子串
 * 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 *
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：
 * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
 * 输出的顺序不重要, [9,0] 也是有效答案。
 * 示例 2：
 *
 * 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
 * 输出：[]
 * 示例 3：
 *
 * 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
 * 输出：[6,9,12]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 由小写英文字母组成
 * 1 <= words.length <= 5000
 * 1 <= words[i].length <= 30
 * words[i] 由小写英文字母组成
 *
 * 备注：该方法不是特别优化，需要优化，目前合格率为 50%
 */
public class Q30 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> list = solution.findSubstring("barfoothefoobarman", new String[]{"foo", "bar"});
        System.out.println(list);
    }


    static class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> ans = new ArrayList<>();
            // 判空
            if (words == null || words.length == 0 || s == null || s.length() == 0) {
                return ans;
            }

            // 初始化
            Map<String, Integer> map = new HashMap<>();
            int oneLen = words[0].length();
            int wordLen = words.length;
            int allLen = oneLen * wordLen;

            // 长度不够
            if (s.length() < allLen)  return ans;

            for (String w : words) {
                // 不存在子字符串
                if (!s.contains(w))  return ans;
                map.put(w, map.getOrDefault(w, 0) + 1);
            }

            for (int i = 0; i < s.length() - allLen + 1; i++) {
                Map<String, Integer> subMap = new HashMap<>();
                int idx = i;
                while (idx < i + allLen) {
                    // 获取一个词
                    String curWord = s.substring(idx, idx + oneLen);
                    // 如果不存在 || 已经存在且次数匹配足够
                    if (!map.containsKey(curWord) || Objects.equals(subMap.get(curWord), map.get(curWord))) {
                        break;
                    }
                    subMap.put(curWord, subMap.getOrDefault(curWord, 0) + 1);
                    idx += oneLen;
                }
                if (idx == i + allLen) {
                    ans.add(i);
                }
            }
            return ans;
        }
    }

}
